import java.util.*;

public class LCP07 {
    class Element{
        int loc;
        int step;

        public Element(int loc, int step) {
            this.loc = loc;
            this.step = step;
        }
    }

    public int numWays(int n, int[][] relation, int k) {
        int res=0;
        Map<Integer, List<Integer>> map=new HashMap<>();
        for (int[] tmp:relation) {
            List<Integer> tmpList = map.getOrDefault(tmp[0],new ArrayList<>());
            tmpList.add(tmp[1]);
            map.put(tmp[0],tmpList);
        }
        Queue<Element> q=new LinkedList();
        q.add(new Element(0,0));
        while(!q.isEmpty()){
            Element ele=q.poll();
            int tmpStep = ele.step;
            int tmpLoc=ele.loc;
            if(tmpStep==k&&ele.loc==n-1){
                res++;
            }
            else if(tmpStep>k){
                break;
            }
            for (Integer locCanReach:map.getOrDefault(tmpLoc,new ArrayList<>())) {
                q.offer(new Element(locCanReach,tmpStep+1));
            }
        }
        return res;
    }
}
